#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//typedef char DataType;
#include"SeqStack.h"
#include"SeqStack.c"
#define MAXSIZE 50
typedef struct 
{
    float data[MAXSIZE];
    int top;
}OpStack;
void TranslateExpress(char s1[],char s2[]);
float ComputeExpress(char s[]);
int main()
{
    freopen("in.txt","r",stdin);
    char a[MAXSIZE],b[MAXSIZE];
    float f;
    printf("请输入一个算数表达式\n");
    gets(a);
    printf("中缀表达式为\n");
    TranslateExpress(a,b);
    printf("%s\n",a);
    printf("后缀表达式\n");
    printf("%s\n",b);
    f = ComputeExpress(b);
    printf("计算结果：\n");
    printf("%f\n",f);
}
float ComputeExpress(char a[])
{
    OpStack S;
    int i = 0,value;
    float x1,x2;
    float result;
    S.top = 0;
    while(a[i] != '\0')
    {
        if(a[i] != ' ' && a[i] >= '0' && a[i] <= '9')
        {
            value = 0;
            while (a[i] != ' ')
            {
                value=10*value + a[i]-'0';
                i++;
            }
            S.data[S.top] = value;
            S.top++;
        }
        else
        {
            switch (a[i])
            {
                case '+':
                    x1 = S.data[S.top-1];
                    S.top--;
                    x2 = S.data[S.top-1];
                    S.top--;
                    result = x2 + x1;
                    S.data[S.top] = result;
                    S.top++;
                   // printf("%f\n",result);
                    break;
                case '-':
                    x1 = S.data[S.top-1];
                    S.top--;
                    x2 = S.data[S.top-1];
                    S.top--;
                    result = x2 - x1;
                    S.data[S.top] = result;
                    S.top++;
                    //printf("%f\n",result);
                    //printf("%d\n",S.top);
                    break;
                case '*':
                    x1 = S.data[S.top-1];
                    S.top--;
                    x2 = S.data[S.top-1];
                    S.top--;
                    result = x2 * x1;
                    S.data[S.top] = result;
                    S.top++;
                    //printf("%f\n",result);
                    break;
                case '/':
                    x1 = S.data[S.top-1];
                    S.top--;
                    x2 = S.data[S.top-1];
                    S.top--;
                    result = x2 / x1;
                    S.data[S.top] = result;
                    S.top++;
                    //printf("%f\n",result);
                    break;
                default:
                    break;
            }
            i++;
        }
    }
    if(S.top != 0)
    {
        result = S.data[S.top - 1];
        S.top--;
        if(0 == S.top)
        {
            return result;
        }
        else
        {
            printf("表达式错误\n");
            exit(-1);
        }
    }
}

void TranslateExpress(char str[], char exp[])
{
    LinkStack S;
    char ch;
    DataType e;
    int i = 0;
    int j = 0;
    S = InitStack(S);
    ch = str[i];
    i++;
    while (ch != '\0')
    {
        switch (ch)
        {
            case '(':
                PushStack(S,'(');
                break;
            case ')':
                while (GetStackTop(S,&e) && e != '(')
                {
                    PopStack(S,&e);
                    exp[j++] = e;
                    exp[j++] = ' ';
                }
                PopStack(S,&e);
                break;
            case '+':
            case '-':
                while(!StackEmpty(S) && GetStackTop(S,&e) && e != '(')
                {
                    PopStack(S,&e);
                    exp[j++] = e;
                    exp[j++] = ' ';
                }
                PushStack(S,ch);
                break;
            case '*':
            case '/':
                while(!StackEmpty(S) && GetStackTop(S,&e) && (e == '*' || e == '/'))
                {
                    PopStack(S,&e);
                    exp[j++] = e;
                    exp[j++] = ' ';
                }
                PushStack(S,ch);
                break;
            default:
                while(ch >= '0' && ch <= '9')
                {
                    exp[j++] = ch;
                    ch = str[i++];
                }
                i--;
                exp[j++] = ' ';
                break;
        }
        ch = str[i++];
    }
    while(!StackEmpty(S))
    {
        PopStack(S,&e);
        exp[j++] = e;
        exp[j++] = ' ';
    }
    exp[j] = '\0';
}